1. Field of the Invention
This invention relates to an image encoding and decoding method, image encoding and decoding device, and more specifically, to a method of synthesizing interframe predicted images by calculating motion vectors of pixels in an image, by performing interpolation/extrapolation of motion vectors of representative points.
2. Background of the Invention:
In high efficiency encoding of a moving image, it is known that interframe prediction (motion compensation) which uses similarities between frames produced at different times has a major effect on data compression. The motion compensating system that has become the mainstream of current image encoding technique is the block matching scheme adopted in H.261, MPEG 1 and MPEG 2 which are the international standards for moving image coding. In this system, the image to be encoded is divided into a large number of blocks, and motion vectors are calculated for each block.
Block matching is currently the most widely used compensation technique, but when the whole image is enlarged, reduced or rotated, motion vectors have to be transmitted for all blocks so the coding efficiency is poor. To deal with this problem, global motion compensation has been proposed wherein the motion vectors of the whole image are represented by a smaller number of parameters (e.g. M. Hotter, “Differential estimation of the global motion parameters zoom and pan”, Signal Processing, vol. 16, no. 3, pp. 249–265, March 1989). In this system, the motion vector (ug(x,y), vg(x,y)) of a pixel (x, y) is expressed in the form:ug(x,y)=a0x+a1y+a2 vg(x,y)=a3x+a4y+a5  (1)orug(x,y)=b0xy+b1x+b2y+b3 vg(x,y)=b4xy+b5x+b6y+b7  (2)and motion compensation is performed using this motion vector. Herein, a0–a5, b0–b7 are the motion parameters. When motion compensation is performed, the predicted image on the transmitting side and receiving side must be the same. For this purpose, the transmitting side can transmit the values of a0–a5 and b0–b7 directly to the transmitting side, however the motion vectors of plural representative points may be transmitted instead. Assume that the coordinates of pixels at the upper left, upper right, lower left and lower right corners of an image are respectively (0,0), (r,0), (0,s), (r,s) where r and s are positive integers. If the horizontal and vertical components of the motion vectors of the representative points (0,0), (r,0), (0,s) are respectively (ua,va), (ub,vb), (uc,vc), equation (1) may be rewritten as:                                                                                           u                  g                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                            ⁢                                                                                                                  u                        b                                            -                                              u                        a                                                              r                                    ⁢                  x                                +                                                                                                    u                        c                                            -                                              u                        a                                                              s                                    ⁢                  y                                +                                  u                  a                                                                                                                                          v                  g                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                            ⁢                                                                                                                  v                        b                                            -                                              v                        a                                                              r                                    ⁢                  x                                +                                                                                                    v                        c                                            -                                              v                        a                                                              s                                    ⁢                  y                                +                                  v                  a                                                                                        (        3        )            
This means that the same functions can be achieved by transmitting ua, va, ub, vb, uc, vc, instead of a0–a5. In the same way, using the horizontal and vertical components (ua,va), (ub,vb), (uc,vc), (ud,vd) of the motion vectors of the four representative points (0,0), (r,0), (0,s), (r,s), equation (2) may be rewritten as:                                                                                           u                  g                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                            ⁢                                                                                          s                      -                      y                                        s                                    ⁢                                      (                                                                                                                        r                            -                            x                                                    r                                                ⁢                                                  u                          a                                                                    +                                                                        x                          r                                                ⁢                                                  u                          b                                                                                      )                                                  +                                                                                                      ⁢                                                y                  s                                ⁢                                  (                                                                                                              r                          -                          x                                                r                                            ⁢                                              u                        c                                                              +                                                                  x                        r                                            ⁢                                              u                        d                                                                              )                                                                                                        =                            ⁢                                                                                                                  u                        a                                            -                                              u                        b                                            -                                              u                        c                                            +                                              u                        d                                                              rs                                    ⁢                  xy                                +                                                                                                    -                                                  u                          a                                                                    +                                              u                        b                                                              r                                    ⁢                  x                                +                                                                                                    -                                                  u                          a                                                                    +                                              u                        c                                                              s                                    ⁢                  y                                +                                  u                  a                                                                                                                                          v                  g                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                            ⁢                                                                                                                  v                        a                                            -                                              v                        b                                            -                                              v                        c                                            +                                              v                        d                                                              rs                                    ⁢                  xy                                +                                                                                                    -                                                  v                          a                                                                    +                                              v                        b                                                              r                                    ⁢                  x                                +                                                                                                    -                                                  v                          a                                                                    +                                              v                        c                                                              s                                    ⁢                  y                                +                                  v                  a                                                                                        (        4        )            
Therefore, the same functions can be achieved by transmitting ua, va, ub, vb, uc, vc, ud, vd instead of b0–b7. This situation is shown by FIG. 1. If global motion compensation is performed between an original image 102 and a reference image 101 in the current frame, motion vectors 107, 108, 109, 110 of representative points 103, 104, 105, 106 (wherein motion vectors are defined as starting at points in the original image and terminating at corresponding points in the reference image of the current frame), may be transmitted instead of the motion parameters. In this specification, the system using equation (1) is referred to as global motion compensation based on linear interpolation/extrapolation, and the system using equation (2) is referred to as global motion compensation based on bilinear interpolation/extrapolation.
Warping prediction is the application of this global movement compensation processing to a smaller area of the image. An example of warping prediction using bilinear interpolation/extrapolation is shown in FIG. 2. FIG. 2 shows processing to synthesize a predicted image of an original image 202 of a current frame using a reference image 201. First, the original frame image 202 is divided into plural polygon-shaped patches to give a patched image 209. The apex of a patch is referred to as a lattice point, and each lattice point is common to plural patches. For example, a patch 210 comprises lattice points 211, 212, 213, 214, and these lattice points are also the apices of other patches. After dividing the image into plural patches in this way, motion estimation is performed. In the example shown here, motion estimation is performed on lattice points using the reference image 201. As a result, each patch in a reference image 203 obtained after motion estimation is transformed. For example, the patch 210 corresponds to a transformed patch 204. This is because, in motion estimation, it was estimated that the lattice points 205, 206, 207, 208 corresponded to 211, 212, 213, 214.
The motion vectors of the lattice points are thereby found, and an interframe predicted image is synthesized by calculating the motion vector for each pixel in the patch by bilinear interpolation. The processing of this warping prediction is basically the same as the global motion compensation shown in FIG. 1, and the “motion vectors at the corners of the image” are transformed into “motion vectors of the lattice points”. If a triangular patch is used instead of a rectangular patch, warping prediction may be realized by linear interpolation/extrapolation.
Examples of encoding and decoding techniques to simplify global motion compensation for representing motion vectors of the whole image using a small number of parameters may be found in the applicant's inventions “Image Encoding and Decoding Methods” (Japanese Unexamined Patent Publication: Application No. Hei 8-60572) and “Methods of Synthesizing Interframe predicted images” (Japanese Unexamined Patent Publication: Application No. Hei 8-249601).
By introducing global motion compensation or warping prediction described above, the motion of the image can be expressed with fewer parameters, and a high data compression rate can be achieved. However, the processing amount in encoding and decoding is greater than in the conventional method. In particular, the divisions of equations (3) and (4) are major factors in making the processing complex. In other words, in global motion compensation or warping prediction, a problem arises in that the processing amount required to synthesize predicted images is large.